class Solution {
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size(), ret = 0;
        vector<vector<bool>> vis(m, vector<bool>(n, false)); // 下标是否被访问过
        queue<vector<int>> q; // 存下标的队列
        q.push(entrance);   // 入口入队
        vis[entrance[0]][entrance[1]] = true;
        while(!q.empty())
        {
            ++ret; // 一层加一次步数
            int size = q.size();
            for(int i = 0; i < size; ++i) // 访问当前层
            {
                vector<int> tmp = q.front();
                q.pop();
                for(int j = 0; j < 4; ++j)
                {
                    int x = tmp[0] + dx[j], y = tmp[1] + dy[j];
                    if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !vis[x][y])
                    {
                        if(x == 0 || x == m - 1 || y == 0 || y == n - 1)
                            return ret; // 是出口就返回
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};